\section{Конверсия строки в число (atoi())}

\myindex{\CStandardLibrary!atoi()}
Попробуем реализовать стандарту функцию Си atoi().

\subsection{Простой пример}

Это самый простой способ прочитать число, представленное в кодировке \ac{ASCII}.

Он не защищен от ошибок: символ отличный от цифры приведет к неверному результату.

\lstinputlisting[style=customc]{\CURPATH/atoi.c}

То, что делает алгоритм это просто считывает цифры слева направо.

Символ нуля в \ac{ASCII} вычитается из каждой цифры.

Цифры от \q{0} до \q{9} расположены по порядку в таблице \ac{ASCII}, так что мы даже можем
и не знать точного значения символа \q{0}.

Всё что нам нужно знать это то что \q{0} минус \q{0} --- это 0, а \q{9} минус \q{0} это 9, итд.

Вычитание \q{0} от каждого символа в итоге дает число от 0 до 9 включительно.

Любой другой символ, конечно, приведет к неверному результату!

Каждая цифра добавляется к итоговому результату (в переменной \q{rt}), но итоговый результат
также умножается на 10 на каждой цифре.

Другими словами, на каждой итерации, результат сдвигается влево на одну позицию в десятичном виде.

Самая последняя цифра прибавляется, но не сдвигается.

\subsubsection{\Optimizing MSVC 2013 x64}

\lstinputlisting[caption=\Optimizing MSVC 2013 x64,style=customasmx86]{\CURPATH/atoi.asm.MSVC2013.x64.Ox_RU}

Символы загружаются в двух местах: первый символ и все последующие символы.

Это сделано для перегруппировки цикла.
\myindex{x86!\Instructions!LEA}
Здесь нет инструкции для умножения на 10, вместо этого две LEA делают это же.

\myindex{x86!\Instructions!ADD}
\myindex{x86!\Instructions!SUB}
MSVC иногда использует инструкцию ADD с отрицательной константой вместо SUB.

Это тот случай.
Честно говоря, трудно сказать, чем это лучше, чем SUB.

Но MSVC делает так часто.

\subsubsection{\Optimizing GCC 4.9.1 x64}

\Optimizing GCC 4.9.1 более краток, но здесь есть одна лишняя инструкция RET в конце.

Одной было бы достаточно.

\lstinputlisting[caption=\Optimizing GCC 4.9.1 x64,style=customasmx86]{\CURPATH/atoi.s.GCC491.O3.x64_RU}

\subsubsection{\OptimizingKeilVI (\ARMMode)}

\lstinputlisting[caption=\OptimizingKeilVI (\ARMMode),style=customasmARM]{\CURPATH/atoi.s.ARM.O3_RU}

\subsubsection{\OptimizingKeilVI (\ThumbMode)}

\lstinputlisting[caption=\OptimizingKeilVI (\ThumbMode),style=customasmARM]{\CURPATH/atoi.s.thumb.O3_RU}

Интересно, из школьного курса математики мы можем помнить, что порядок операций сложения и вычитания
не играет роли.

Это наш случай: в начале вычисляется выражение $rt*10 - '0'$, затем к нему прибавляется 
значение входного символа.

Действительно, результат тот же, но компилятор немного всё перегруппировал.

\subsubsection{\Optimizing GCC 4.9.1 ARM64}

Компилятор для ARM64 может использовать суффикс инструкции, задающий пре-инкремент:

\lstinputlisting[caption=\Optimizing GCC 4.9.1 ARM64,style=customasmARM]{\CURPATH/atoi.s.GCC49.ARM64.O3_RU}

\subsection{Немного расширенный пример}

Новый пример более расширенный, теперь здесь есть проверка знака \q{минус} в самом начале,
и еще он может сообщать об ошибке если не-цифра была найдена во входной строке:

\lstinputlisting[style=customc]{\CURPATH/atoi2.c}

\subsubsection{\Optimizing GCC 4.9.1 x64}

\lstinputlisting[caption=\Optimizing GCC 4.9.1 x64,style=customasmx86]{\CURPATH/atoi2.s.GCC491.O3.x64_RU}

\myindex{x86!\Instructions!NEG}
Если знак \q{минус} был найден в начале строки, инструкция NEG будет исполнена в конце.

Она просто меняет знак числа.

\label{one_comparison_instead_of_two}
Еще кое-что надо отметить.
Как среднестатистический программист будет проверять, является ли символ цифрой?

Так же, как и у нас в исходном коде:

\begin{lstlisting}[style=customc]
if (*s<'0' || *s>'9')
    ...
\end{lstlisting}

Здесь две операции сравнения.
Но что интересно, так это то что мы можем заменить обе операции на одну:

просто вычитайте \q{0} из значения символа,
считается результат за беззнаковое значение (это важно) и проверьте, не больше ли он чем 9.

Например, скажем, строка на входе имеет символ точки (\q{.}), которая имеет код 46 в таблице \ac{ASCII}.

$46-48=-2$ если считать результат за знаковое число.
Действительно, символ точки расположен на два места раньше, чем символ \q{0} в таблице \ac{ASCII}.

Но это \TT{0xFFFFFFFE} (4294967294) если считать результат за беззнаковое значение, 
и это точно больше чем 9!

Компиляторы часто так делают, важно распознавать эти трюки.

Еще один пример подобного в этой книге: 
\myref{toupper_one_comparison}.

\Optimizing MSVC 2013 x64 применяет те же трюки.

\subsubsection{\OptimizingKeilVI (\ARMMode)}

\lstinputlisting[caption=\OptimizingKeilVI (\ARMMode),numbers=left,style=customasmARM]{\CURPATH/atoi2.s.ARM.O3_RU}

В 32-битном ARM нет инструкции NEG, так что вместо этого используется операция \q{Reverse Subtraction}
(строка 31).

Она сработает если результат инструкции CMP (на строке 29) был \q{Not Equal} 
(не равно, отсюда суффикс -NE suffix).

\myindex{ARM!\Instructions!RSB}
Что делает RSBNE это просто вычитает результирующее значение из нуля.

Она работает, как и обычное вычитание, но меняет местами операнды.

Вычитание любого числа из нуля это смена знака: $0-x=-x$.

Код для режима Thumb почти такой же.

\myindex{ARM!\Instructions!NEG}
GCC 4.9 для ARM64 может использовать инструкцию NEG, доступную в ARM64.

\subsection{\Exercise{}}

\myindex{Fuzzing}

Кстати, security research-еры часто имеют дело с непредсказуемым поведением программ во время обработки некорректных данных.
Например, во время fuzzing-а.

В качестве упражнения, вы можете попробовать ввести символы не относящиеся к числам и посмотреть, что случится.

Попробуйте объяснить, что произошло, и почему.


